class Solution:
    MAX_INT = 10001

    def superEggDrop(self, k: int, n: int) -> int:
        # 定义状态矩阵：dp[i][j] = i个蛋、j层楼的最小次数（因为每次转移只会用到i-1的情况，所以省略i）
        # 初始化状态矩阵：当蛋只有1个时，只能从下往上一层一层试
        dp1 = [i for i in range(n + 1)]

        # 状态转移：递增蛋的数量计算
        # dp[i][j] = max(dp[i][j2],dp[i-1][j1-j2])+1
        for i in range(2, k + 1):
            # 初始化状态矩阵
            dp2 = list(dp1)

            # 计算上一层蛋数已支持完全二分的层数：这一层只需要更新，上一层的蛋不支持完全二分的层数
            bisect_floor = pow(2, i - 1) - 1

            # 遍历2层及以上楼层的情况
            j2 = 0  # 第1次尝试的楼层
            for j1 in range(bisect_floor + 1, n + 1):
                # 如果提高第1次测试的楼层后，仍然是下面楼层所需后续测试少，上面楼层所需后续测试多，那么就提高第1次测试的楼层
                # 循环结束后：dp2[j2-1]>dp1[j1-j2] -> 即下面楼层所需的测试次数多，上面楼层所需的测试次数少
                while j2 + 1 < j1 and dp2[j2] <= dp1[j1 - j2 - 1]:
                    j2 += 1

                # 计算当前楼层所需的测试次数：下面楼层所需后续测试次数多于上面楼层所需后续测试多的情况（原因未证明）
                dp2[j1] = 1 + max(dp2[j2 - 1], dp1[j1 - j2])

            dp1 = dp2

        return dp1[-1]


if __name__ == "__main__":
    print(Solution().superEggDrop(1, 2))  # 2
    print(Solution().superEggDrop(2, 6))  # 3
    print(Solution().superEggDrop(3, 14))  # 4

    # 自制用例
    print(Solution().superEggDrop(1, 1))  # 1
    print(Solution().superEggDrop(3, 15))  # 5
    print(Solution().superEggDrop(2, 3))  # 2
    print(Solution().superEggDrop(3, 7))  # 2
